package leetcode.ArrayAndString;

public class AddBinary {

    public static  String addBinary(String a, String b) {
        StringBuffer result=new StringBuffer();
        int sum=0;
        int lengthA=a.length();
        int lengthB=b.length();
        while(lengthA>0||lengthB>0){
            if(lengthA>0){
                //截取字符串最后一位，类似获取十进制里的个位
                sum+=Integer.parseInt(a.substring(lengthA-1,lengthA));
                lengthA--;
            }
            if(lengthB>0){
                sum+=Integer.parseInt(b.substring(lengthB-1,lengthB));
                lengthB--;
            }
            //当刚好满足二进制进位条件时
            if(sum==2){
                //相加刚好等于2，所以前一位剩余0，类似于十进制 4+6时，个位满十进位，个位数值为0
                result.insert(0,"0");
                //这里重新赋予1，是指进位的那一个数值，所以前面代码是用 sum+=  而不是sum=
                sum=1;
            }else if(sum==3){
                result.insert(0,"1");
                sum=1;
            }else{
                result.insert(0,sum+"");
                sum=0;
            }
        }
        //用于处理最高位进位
        if(sum==1){
            result.insert(0,"1");
        }
        return result.toString();
    }

    public static String betterAddBinary(String a ,String b){
        if(a==null) return b;
        if(b==null) return a;

        //String 转 char[]
        char[] aArray=a.toCharArray();
        char[] bArray=b.toCharArray();
        int aLen=aArray.length;
        int bLen=bArray.length;
        //创建返回结果的char[]
        char[] resultArray=new char[aLen>bLen?aLen+1:bLen+1];
        int carry=0;
        int i=aLen-1;  //String a 的末尾指针
        int j=bLen-1;  //String b 的末尾指针
        int k=resultArray.length-1;  // 结果的末尾指针

        while(i>=0||j>=0||carry>0){
            int total=carry;
            if(i>=0) total=total+aArray[i]-'0';
            if(j>=0) total=total+bArray[j]-'0';
            carry=total/2;
            resultArray[k] = (char)(total%2+'0');
            k--;
            i--;
            j--;
        }
        k=0;
        while(k<resultArray.length&&(resultArray[k]==0||resultArray[k]=='0')){
            k++;
        }
        if(k<resultArray.length)
            return new String(resultArray,k,resultArray.length-k);
        return new String("0");
    }

    public static void main(String[] args) {


        long start = System.currentTimeMillis();
        for (int i = 0; i <10000 ; i++) {
//            addBinary("11110001011100111","11111100000110101");
            betterAddBinary("11110001011100111","11111100000110101");
        }

//        System.out.println(addBinary("111","111"));
        long end = System.currentTimeMillis();

        System.out.println("time = " + (end - start));
    }
}
